<?php
// +----------------------------------------------------------------------
// | 算法四：回溯法 ( Back Tracking ) (通用解题法)
// | 基本思想：
// | 步骤：
// |   1）针对所给问题，定义问题的解空间。
// |   2）确定易于搜索的解空间结构。
// |   3）以深度优先的方式搜索解空间。
// | 典型实例：
// |   1）0-1背包问题  O(n)
// |   2）n皇后问题    O(n)
// +----------------------------------------------------------------------
namespace helper\algorithm;

class BackTracking
{
    public function demo()
    {
        $n = 8;
        $w = 110;
        $values = [11, 21, 31, 33, 43, 53, 55, 65];
        $weights = [1, 11, 21, 23, 33, 43, 45, 55];
        $vw = [];
        foreach ($values as $k=>$v) {
            $vw[] = round($v/$weights[$k], 1);
        }
        $res = $this->knapsack($values, $weights, $vw, $n, $w);
        print_r($res);
    }

    /**
     *
     * @param array $values
     * @param array $weights
     * @param array $vw
     * @param int $n
     * @param int $w
     * @param float $profit_gained 已经获得的价值
     * @param int $weight_used 已经获得背包从重量
     * @param int $k 已经确定的物品
     * @return float
     */
    public function bound(array $values, array $weights, array $vw, int $n, int $w, float $profit_gained,
                          int   $weight_used, int $k)
    {
        for ($i = $k + 1; $i < $n; $i++) {
            if ($weight_used + $weights[$i] <= $w) {
                $profit_gained += $values[$i];
                $weight_used   += $weights[$i];
            } else {
                $profit_gained += $vw[$i] * ($w - $weight_used);
                $weight_used   = $w;
                return $profit_gained;
            }
        }
        return $profit_gained;
    }

    /**
     * 0-1 背包问题
     * @param array $values 价值数组
     * @param array $weights 重量数组
     * @param array $vw
     * @param int $n 物品数
     * @param int $w 背包总重量
     * @return array
     */
    public function knapsack(array $values, array $weights, array $vw, int $n, int $w): array
    {
        $current_weight = 0;
        $current_profit = 0;
        $weight         = 0;//获得最大价值时物品重量
        $profit         = -1;//获得最大价值
        $index          = 0;
        $X              = [];//问题的最优解
        $Y              = [];

        while (true) {
            while ($index < $n && $current_weight + $weights[$index] <= $w) {
                $current_profit += $values[$index];
                $current_weight += $weights[$index];
                $Y[$index]      = 1;
                $index++;
            }
            if ($index >= $n) {
                $weight = $current_weight;
                $profit = $current_profit;
                $index  = $n;
                for ($i = 0; $i < $n; $i++) {
                    $X[$i] = $Y[$i];
                }
            } else {
                $Y[$index] = 0;
            }

            while ($this->bound($values, $weights, $vw, $n, $w, $current_profit, $current_weight, $index) <= $profit) {
                // 向前回溯
                while ($index >= $n || $index != 0 && $Y[$index] != 1) {
                    $index--;
                }
                // 输出结果
                if ($index == 0) {
                    return ['x' => $X, 'weight' =>$weight, 'profit' => $profit];
                }
                $Y[$index]      = 0;
                $current_profit -= $values[$index];
                $current_weight -= $weights[$index];
            }
            $index++;
        }
    }
}